/**
 * @param {number[][]} grid
 * @param {number} stampHeight
 * @param {number} stampWidth
 * @return {boolean}
 */
 var possibleToStamp = function(grid, stampHeight, stampWidth) {
  const m = grid.length, n = grid[0].length;
  const sum = new Array(m+1).fill().map(() => new Array(n+1).fill(0))
  for(let i = 1; i<=m; i++){
    for(let j = 1; j<=n; j++){
      sum[i][j] = grid[i-1][j-1] ^ 1 + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1]
    }
  }
  const bool = new Array(m).fill().map(() => new Array(n).fill(false))
  // i, j 为左上角
  const check = (i, j, h, w) => {
    if(i > m || j > n) return false
    let r = i+h, c = j+w
    if(r > m || c > n) return false
    let s = sum[r][c] - sum[r][j] - sum[i][c] + sum[i][j]
    return s === h * w
  }
  const change = (i, j) => {
    let dx = stampHeight-1, dy = stampWidth-1
    // for(let x = i+dx; x>=i; x--){
    for(let x = i; x<i+dx; x++){
      for(let y = j+dy; y>=j; y--){
        if(bool[x][y]) break
        bool[x][y] = true
      }
    }
    return true
  }
  for(let i = 0; i<m; i++){
    for(let j = 0; j<n; j++){
      if(grid[i][j] === 1) continue
      if(check(i,j,stampHeight, stampWidth)) change(i, j)
      if(!bool[i][j]) return false
    }
  }
  return true
};